package com.example.demo.tree;

import com.example.demo.entity.TreeNode;
import org.junit.jupiter.api.Test;

public class ValidBST {

    private TreeNode buildTreeNode() {
        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode nodeD = new TreeNode(4);
        TreeNode nodeE = new TreeNode(5);
        TreeNode nodeF = new TreeNode(6);

        root.left = node2;
        root.right = nodeD;

        node2.left = node1;

        nodeD.left = nodeE;
        nodeE.left = nodeF;

        return root;
    }

    /**
     * 验证是否是二叉搜索树，递归
     */
    @Test
    public void ValidBST() {
        TreeNode root = buildTreeNode();
        boolean valid = isValid(root, null, null);
        if (valid) {
            System.out.println("是二叉搜索树");
        } else {
            System.out.println("不是二叉搜索树");
        }
    }

    // 思想“左子树和右子树都是二叉搜索树”
    private boolean isValid(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;
        if (min != null && node.val <= min) return false;
        if (max != null && node.val >= max) return false;
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }

    /**
     * 验证是否是二叉搜索树，中序遍历，中序遍历是升序
     */
    @Test
    public void ValidBST2() {
        TreeNode root = buildTreeNode();
        inOrder(root);
        if (isValidBST) {
            System.out.println("是二叉搜索树");
        } else {
            System.out.println("不是二叉搜索树");
        }
    }

    private static boolean isValidBST = true;
    private static Integer prev = Integer.MIN_VALUE;

    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            if (node.val < prev) {
                isValidBST = false;
                return;
            }
            prev = node.val;
            inOrder(node.right);
        }
    }
}
